{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### POS(Part of Speech) 词性标注"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 句子，一行一个单词，是完整的句子\n",
    "train_file = \"data/traindata.txt\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Numberic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "tag2id, id2tag = {}, {}\n",
    "word2id, id2word = {}, {}\n",
    "\n",
    "for line in open(train_file):\n",
    "    items = line.split(\"/\")\n",
    "    word, tag = items[0], items[1].rstrip()\n",
    "\n",
    "    if word not in word2id:\n",
    "        word2id[word] = len(word2id)\n",
    "        id2word[len(id2word)] = word\n",
    "    if tag not in tag2id:\n",
    "        tag2id[tag] = len(tag2id)\n",
    "        id2tag[len(id2tag)] = tag\n",
    "\n",
    "M = len(word2id) # 词典大小\n",
    "N = len(tag2id) # tag的个数，词性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 构建HMM模型\n",
    "- 通过对语料的统计得到HMM的参数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "# 初始状态概率向量, 每个词性(tag)出现在句子中的第一个位置的概率\n",
    "pi = np.zeros(N)\n",
    "# A 转移概率矩阵, A[i][j], 状态(tag) 之间相互转移的概率\n",
    "A = np.zeros((N, N))\n",
    "# 状态(tag) 到观测值(单词) 的概率\n",
    "B = np.zeros((N, M))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "prev_tag = \"\"\n",
    "for line in open(train_file):\n",
    "    items = line.split(\"/\")\n",
    "    wordId, tagId = word2id[items[0]], tag2id[items[1].rstrip()]\n",
    "\n",
    "    # 句子开头\n",
    "    if prev_tag == \"\":\n",
    "        # 更新 初始状态概率向量\n",
    "        pi[tagId] += 1\n",
    "        # 更新发射矩阵\n",
    "        B[tagId][wordId] += 1\n",
    "    else:\n",
    "        A[tag2id[prev_tag]][tagId] += 1\n",
    "        B[tagId][wordId] += 1\n",
    "    \n",
    "    # 这里设置 prev_tag 给下一轮用\n",
    "    if items[0] == \".\":\n",
    "        prev_tag = \"\"\n",
    "    else:\n",
    "        prev_tag = items[1].rstrip()\n",
    "\n",
    "# normalize 计算概率\n",
    "pi = pi/sum(pi)\n",
    "# 按行计算， 完成了HMM 的构建\n",
    "for i in range(N):\n",
    "    A[i] /= sum(A[i]) # 行\n",
    "    B[i] /= sum(B[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def log(v):\n",
    "    if v == 0:\n",
    "        # 平滑操作\n",
    "        return np.log(v+0.000001)\n",
    "    return np.log(v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 求解问题\n",
    "- 给定另一个句子求解每个单词的词性\n",
    "- 给定观测序列，求解状态序列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def viterbi(x, pi, A, B):\n",
    "    # OOV\n",
    "    x = [word2id[word] for word in x.split(\" \")] # numberic\n",
    "    T = len(x)\n",
    "\n",
    "    # 记录每个时刻，在每个状态上的最优打分\n",
    "    dp = np.zeros((T, N))\n",
    "    # T * N ， 每个状态记录从前面哪个状态转移过来的\n",
    "    ptr = np.array([[0 for x in range(N)] for y in range(T)])\n",
    "\n",
    "    # T = 0 时刻的状态\n",
    "    for j in range(N):\n",
    "        # 初始状态\n",
    "        dp[0][j] = log(pi[j]) + log(B[j][x[0]])\n",
    "\n",
    "    for i in range(1, T):\n",
    "        # 当前时刻状态j\n",
    "        for j in range(N):\n",
    "            # 初始化一个极小的打分\n",
    "            dp[i][j] = -9999999\n",
    "            # 计算从每个k到j的打分\n",
    "            for k in range(N):\n",
    "                score = dp[i-1][k] + log(A[k][j]) + log(B[j][x[i]])\n",
    "                if score > dp[i][j]:\n",
    "                    # 更新打分\n",
    "                    dp[i][j] = score\n",
    "                    # 记录转移路径, i时刻最优解是从k --> j\n",
    "                    ptr[i][j] = k\n",
    "\n",
    "\n",
    "    best_seq = [0]*T\n",
    "    # 找到最后一个时刻打分最高的点，再往前推\n",
    "    best_seq[T-1] = np.argmax(dp[T-1])\n",
    "\n",
    "    for i in range(T-2, -1, -1):\n",
    "        # ptr[i+1][最优的打分的 状态] 记录的就是前一时刻从哪个点转移过来\n",
    "        best_seq[i] = ptr[i+1][best_seq[i+1]] # 得到打分最优时，i时刻的状态\n",
    "    for i in range(len(best_seq)):\n",
    "        print(id2tag[best_seq[i]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NNP\n",
      "NNP\n",
      "NN\n",
      ",\n",
      "NN\n",
      "NN\n",
      "CC\n",
      "NNS\n",
      "IN\n",
      "DT\n",
      "NNS\n",
      "VBN\n",
      "IN\n",
      "DT\n",
      "NN\n"
     ]
    }
   ],
   "source": [
    "x = \"Social Security number , passport number and details about the services provided for the payment\"\n",
    "viterbi(x, pi, A, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "ecf5722fdaf1897a315d257d89d94520bfcaa453217d5becf09b39e73618b0de"
  },
  "kernelspec": {
   "display_name": "Python 3.9.5 ('base')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.5"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
